/*
 * @Description: Maze Problem BFS
 * @Author: Niezl
 * @Gitee: https://gitee.com/Morphlng
 * @Date: 2021-04-06 14:44:31
 * @LastEditors: Niezl
 * @LastEditTime: 2021-04-07 20:49:24
 */
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

// 0：'O'，1：'X'
int map[4][4] = {
    1, 1, 1, 1,
    1, 0, 0, 1,
    1, 1, 0, 1,
    1, 0, 1, 1};

bool visited[16];

void Flip()
{
    for (int m = 0; m < 16; m++)
        if (visited[m])
            map[m / 4][m % 4] = 1;
}

void print()
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            if (map[i][j] == 1)
                cout << "X"
                     << " ";
            else
                cout << "O"
                     << " ";
        }
        cout << endl;
    }
}

struct vec2
{
    int x, y;
};

bool BFS(int i, int j)
{
    queue<vec2> q;
    q.push({i, j});

    while (!q.empty())
    {
        vec2 curr = q.front();
        q.pop();
        visited[curr.x * 4 + curr.y] = true;
        
        // 能走到边界说明没被包围
        if (curr.x - 1 < 0 || curr.x + 1 > 3 || curr.y - 1 < 0 || curr.y + 1 > 3)
            return true;

        // 左
        if (!visited[curr.x * 4 + curr.y - 1] && map[curr.x][curr.y - 1] == 0)
            q.push({curr.x, curr.y - 1});
        // 右
        if (!visited[curr.x * 4 + curr.y + 1] && map[curr.x][curr.y + 1] == 0)
            q.push({curr.x, curr.y + 1});
        // 上
        if (!visited[(curr.x - 1) * 4 + curr.y] && map[curr.x - 1][curr.y] == 0)
            q.push({curr.x - 1, curr.y});
        // 下
        if (!visited[(curr.x + 1) * 4 + curr.y] && map[curr.x + 1][curr.y] == 0)
            q.push({curr.x + 1, curr.y});
    }
    return false;
}

int main()
{
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (map[i][j] == 0)
            {
                memset(visited, 0, sizeof(visited));
                if (!BFS(i, j))
                    Flip();
            }
    print();
    return 0;
}